package leetcode;

import java.util.HashMap;
import java.util.Map;

public class LeetCode70 {

    //没有数组好 hashMap占用内存大
    Map<Integer, Integer> dict = new HashMap<>();

    public int climbStairs(int n) {
        if (dict.containsKey(n))
            return dict.get(n);
        if (n == 0)
            return 1;
        else if (n < 0)
            return 0;
        int result = climbStairs(n - 2) + climbStairs(n - 1);
        dict.put(n, result);
        return result;
    }

    public int climbStairs1(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }

//------------------------------------------------------------------
}
